package com.ly.algorithm.offerpointer;

/**
 * @Classname Offer26
 * @Description TODO
 * @Date 2021/1/27 17:39
 * @Author 冷心影翼
 */
public class Offer26 {

    public static void main(String[] args) {
        Solution26 solution26 = new Solution26();
        System.out.println(solution26.isSubStructure(TreeNode.init(new int[]{4,2,3,4,5,6,7,8,9}), TreeNode.init(new int[]{4,8,9})));

    }
}

class Solution26 {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(B == null || A == null) {
            return false;
        }
        return isSubStructureRecursive(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }

    private boolean isSubStructureRecursive(TreeNode a, TreeNode b) {
        if(b == null) {
            return true;
        }
        if(a == null) {
            return false;
        }
        if(a.val == b.val) {
            return isSubStructureRecursive(a.left,b.left) && isSubStructureRecursive(a.right,b.right);
        }else {
            return false;
        }
    }
}
